#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <math.h>
#include <algorithm>
using namespace std;
//f(x)=x*x
struct Individual{
    bool bit[5];
    double fit;
    double probability;
    int value;
    Individual():fit(0),value(0),probability(0){
        for(int i=0;i<5;i++){
            bit[i]=rand()%2;
        }
        for(int i=0;i<5;i++){
            value+=bit[4-i]*pow(2,i);
        }
        fit=value*value;
    }
    void show(){
        for(int i=0;i<5;i++){
            cout<<bit[i]<<",";
        }
        cout<<value<<endl;
    }
};

void upData(vector<Individual>&population){
    int size=population.size(),sum=0;
    for(int i=0;i<population.size();i++){
        population[i].value=0;
        for(int j=0;j<5;j++){
            population[i].value+=population[i].bit[4-j]*pow(2,j);
        }
        population[i].fit=pow(population[i].value,2);
    }

    for(int i=0;i<size;i++){
        sum+=population[i].fit;
    }
    for(int i=0;i<size;i++){
        population[i].probability=population[i].fit/sum;
    }
}

void sort(vector<Individual>&population){
    int size=population.size();
    Individual t;
    for(int i=0;i<size;i++){
        for(int j=i+1;j<size;j++){
            if(population[i].probability<=population[j].probability){
                t=population[i];
                population[i]=population[j];
                population[j]=t;
            }
        }
    }
}

void NaturalSelection(vector<Individual>&population){
    upData(population);
    sort(population);
    population[population.size()-1]=population[0];
}

void Mating(vector<Individual>&population){
    int x=rand()%5,y=rand()%5,t=0;
    int size=population.size();
    for(int i=x;i<5;i++){
        t=population[0].bit[i];
        population[0].bit[i]=population[1].bit[i];
        population[1].bit[i]=t;
    }
    for(int i=y;i<5;i++){
        t=population[2].bit[i];
        population[2].bit[i]=population[3].bit[i];
        population[3].bit[i]=t;
    }
    upData(population);
}

void Variation(vector<Individual>&population){
    int x=rand()%4,y=rand()%5;
    population[x].bit[y]=!population[x].bit[y];
    upData(population);
}

int main(){
    srand(time(0));

    vector<Individual>Population(4);

    for(int i=0;i<8;i++){
        NaturalSelection(Population);
        Variation(Population);
        Mating(Population);
    }
    NaturalSelection(Population);
    for(auto temp:Population){
        temp.show();
    }
    return 0;
}